//import java.util.Arrays;
//import java.util.Collection;
//import java.util.Iterator;
//import java.util.List;
//import java.util.ListIterator;
//import java.util.Objects;
//import java.util.function.Predicate;
//
///**
// * 实现一个自己的ArrayList
// *
// * @param <E> 元素类型
// */
//public class MyArrayList<E> implements List<E> {
//
//  /**
//   * 数据容器
//   */
//  private Object[] data;
//  /**
//   * 实际容量
//   */
//  private int size;
//
//  public MyArrayList() {
//    this(10);
//  }
//
//  public MyArrayList(int capacity) {
//    data = new Object[capacity];
//  }
//
//  /**
//   * 将一个元素添加到指定索引
//   *
//   * @param index 索引
//   * @param e 元素
//   */
//  @Override
//  public void add(int index, E e) {
//    rangeCheckForAdd(index);
//    int oldCapacity = data.length;
//    if (oldCapacity == size) {
//      resize(oldCapacity + (oldCapacity >> 1));
//    }
//    System.arraycopy(data, index, data, index + 1, size - index);
//    data[index] = e;
//    size++;
//  }
//
//  /**
//   * 根据索引删除一个元素
//   *
//   * @param index 索引
//   * @return 删除的元素
//   */
//  @Override
//  public E remove(int index) {
//    Objects.checkIndex(index, size);
//    E oldValue = elementData(index);
//    fastRemove(index);
//    return oldValue;
//  }
//
//  /**
//   * 查询元素在容器中索引（从前往后）
//   *
//   * @param o 元素
//   * @return 索引 不存在返回-1
//   */
//  @Override
//  public int indexOf(Object o) {
//    for (int i = 0; i < size; i++) {
//      if (Objects.equals(data[i], o)) {
//        return i;
//      }
//    }
//    return -1;
//  }
//
//  /**
//   * 查询元素在容器中索引（总后往前）
//   *
//   * @param o 元素
//   * @return 索引
//   */
//  @Override
//  public int lastIndexOf(Object o) {
//    for (int i = size - 1; i >= 0; i--) {
//      if (Objects.equals(data[i], o)) {
//        return i;
//      }
//    }
//    return -1;
//  }
//
//  /**
//   * 创建迭代器
//   *
//   * @return 迭代器
//   */
//  @Override
//  public ListIterator<E> listIterator() {
//    return new MyArrayListListIterator(0);
//  }
//
//  /**
//   * 创建迭代器
//   *
//   * @param index 开始索引
//   * @return 迭代器
//   */
//  @Override
//  public ListIterator<E> listIterator(int index) {
//    return new MyArrayListListIterator(index);
//  }
//
//  /**
//   * 创建一个容器的视图
//   *
//   * @param fromIndex 开始索引
//   * @param toIndex 结束索引
//   * @return 容器视图
//   */
//  @Override
//  public List<E> subList(int fromIndex, int toIndex) {
//    subListRangeCheck(fromIndex, toIndex, size);
//    List<E> subList = new MyArrayList<>();
//    for (int i = fromIndex; i < toIndex; i++) {
//      subList.add(elementData(i));
//    }
//    return subList;
//  }
//
//  /**
//   * 添加元素
//   *
//   * @param e 元素
//   * @return 添加是否成功
//   */
//  @Override
//  public boolean add(E e) {
//    add(size, e);
//    return true;
//  }
//
//  /**
//   * 删除元素
//   *
//   * @param o 元素
//   * @return 是否成功
//   */
//  @Override
//  public boolean remove(Object o) {
//    int index = indexOf(o);
//    if (index > -1) {
//      fastRemove(index);
//      return true;
//    }
//    return false;
//  }
//
//  /**
//   * 是否包含指定容器中的所有元素
//   *
//   * @param c 容器
//   * @return 是否包含
//   */
//  @Override
//  public boolean containsAll(Collection<?> c) {
//    for (Object e : c) {
//      if (!contains(e)) {
//        return false;
//      }
//    }
//    return true;
//  }
//
//  /**
//   * 将指定容器中元素全部添加到该容器中
//   *
//   * @param c 容器
//   * @return 是否成功
//   */
//  @Override
//  public boolean addAll(Collection<? extends E> c) {
//    return addAll(size, c);
//  }
//
//  /**
//   * 将指定容器元素添加到指定索引
//   *
//   * @param index 索引
//   * @param c 容器
//   * @return 是否成功
//   */
//  @Override
//  public boolean addAll(int index, Collection<? extends E> c) {
//    rangeCheckForAdd(index);
//    int oldCapacity = data.length;
//    int newSize = size + c.size();
//    if (newSize > oldCapacity) {
//      int newCapacity = oldCapacity;
//      while (newSize > newCapacity) {
//        newCapacity = newCapacity + (newCapacity >> 1);
//      }
//      resize(newCapacity);
//    }
//    System.arraycopy(data, index, data, index + c.size(), size - index);
//    System.arraycopy(c.toArray(), 0, data, index, c.size());
//    size += c.size();
//    return true;
//  }
//
//  /**
//   * 删除指定容器中的所有元素
//   *
//   * @param c 容器
//   * @return 是否成功
//   */
//  @Override
//  public boolean removeAll(Collection<?> c) {
//    batchRemove(item -> !c.contains(item));
//    return true;
//  }
//
//  /**
//   * 保留指定容器中的所有元素，其余的删除
//   *
//   * @param c 容器
//   * @return 是否成功
//   */
//  @Override
//  public boolean retainAll(Collection<?> c) {
//    batchRemove(c::contains);
//    return true;
//  }
//
//  /**
//   * 删除满足指定条件的元素
//   *
//   * @param filter 删除条件
//   * @return 是否成功
//   */
//  @Override
//  public boolean removeIf(Predicate<? super E> filter) {
//    batchRemove(filter.negate());
//    return true;
//  }
//
//  /**
//   * 清空容器
//   */
//  @Override
//  public void clear() {
//    for (int i = 0; i < size; i++) {
//      data[i] = null;
//    }
//    size = 0;
//  }
//
//  /**
//   * 修改指定索引的元素
//   *
//   * @param index 索引
//   * @param e 元素
//   * @return 原来的元素
//   */
//  @Override
//  public E set(int index, E e) {
//    Objects.checkIndex(index, size);
//    E oldValue = elementData(index);
//    data[index] = e;
//    return oldValue;
//  }
//
//  /**
//   * 获取执行索引的元素
//   *
//   * @param index 索引
//   * @return 元素
//   */
//  @Override
//  public E get(int index) {
//    Objects.checkIndex(index, size);
//    return elementData(index);
//  }
//
//  /**
//   * 查询容器容量
//   *
//   * @return 容量
//   */
//  @Override
//  public int size() {
//    return size;
//  }
//
//  /**
//   * 容器是否为空
//   *
//   * @return 是否为空
//   */
//  @Override
//  public boolean isEmpty() {
//    return size == 0;
//  }
//
//  /**
//   * 容器是否包含指定元素
//   *
//   * @param o 元素
//   * @return 是否包含
//   */
//  @Override
//  public boolean contains(Object o) {
//    return indexOf(o) >= 0;
//  }
//
//  /**
//   * 创建迭代器
//   */
//  @Override
//  public Iterator<E> iterator() {
//    return new MyArrayListIterator();
//  }
//
//  /**
//   * 将容器转换成数组
//   *
//   * @return 数组
//   */
//  @Override
//  public Object[] toArray() {
//    return Arrays.copyOf(data, size);
//  }
//
//  /**
//   * 将容器转换成指定类型的数组
//   *
//   * @param a 指定数组
//   * @param <T> 数组元素类型
//   */
//  @Override
//  public <T> T[] toArray(T[] a) {
//    if (a.length < size) {
//      return (T[]) Arrays.copyOf(data, size, a.getClass());
//    }
//    System.arraycopy(data, 0, a, 0, size);
//    if (a.length > size) {
//      a[size] = null;
//    }
//    return a;
//  }
//
//  @Override
//  public String toString() {
//    return Arrays.toString(toArray());
//  }
//
//  private void fastRemove(int index) {
//    System.arraycopy(data, index + 1, data, index, size - index - 1);
//    data[size] = null;
//    size--;
//  }
//
//  private void batchRemove(Predicate<? super E> filter) {
//    int low = 0;
//    int high = 0;
//    for (; high < size; high++) {
//      if (filter.test(elementData(high))) {
//        data[low++] = data[high];
//      }
//    }
//    for (int i = low; i < high; i++) {
//      data[i] = null;
//    }
//    size -= high - low;
//  }
//
//  private void resize(int newCapacity) {
//    Object[] newData = new Object[newCapacity];
//    System.arraycopy(data, 0, newData, 0, size);
//    data = newData;
//  }
//
//  private E elementData(int index) {
//    return (E) data[index];
//  }
//
//  private void rangeCheckForAdd(int index) {
//    if (index > size || index < 0) {
//      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//    }
//  }
//
//  private void subListRangeCheck(int fromIndex, int toIndex, int size) {
//    if (fromIndex < 0) {
//      throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
//    }
//    if (toIndex > size) {
//      throw new IndexOutOfBoundsException("toIndex = " + toIndex);
//    }
//    if (fromIndex > toIndex) {
//      throw new IllegalArgumentException("fromIndex(" + fromIndex +
//          ") > toIndex(" + toIndex + ")");
//    }
//  }
//
//  private String outOfBoundsMsg(int index) {
//    return "Index: " + index + ", Size: " + size;
//  }
//
//  private class MyArrayListIterator implements Iterator<E> {
//
//    int cursor;
//
//    @Override
//    public boolean hasNext() {
//      return cursor != size;
//    }
//
//    @Override
//    public E next() {
//      return elementData(cursor++);
//    }
//
//    @Override
//    public void remove() {
//      MyArrayList.this.remove(cursor);
//    }
//  }
//
//  private class MyArrayListListIterator extends MyArrayListIterator implements ListIterator<E> {
//
//    MyArrayListListIterator(int index) {
//      super();
//      cursor = index;
//    }
//
//    @Override
//    public boolean hasPrevious() {
//      return cursor != 0;
//    }
//
//    @Override
//    public E previous() {
//      return elementData(--cursor);
//    }
//
//    @Override
//    public int nextIndex() {
//      return cursor;
//    }
//
//    @Override
//    public int previousIndex() {
//      return cursor - 1;
//    }
//
//    @Override
//    public void set(E e) {
//      MyArrayList.this.set(cursor, e);
//    }
//
//    @Override
//    public void add(E e) {
//      MyArrayList.this.add(cursor, e);
//    }
//  }
//}
